#include "stdafx.h"
#include "MatrixUtil.h"



//class Matrix
//{	
	
	int getNum(int iLen,int iIndex)
	{
		int iNum = 1;
		for(int i = 0;i< (iLen - iIndex - 1);i++)
		{
			iNum = 10 * iNum;
		}
		return iNum;
	}

	int getNumber(char * str)
	{
		int iLength = strlen(str);
		int iNum = 0;
		int iSum = 0;
		for(int i= 0;i< iLength ;i++)
		{
			if(str[i] - 48 > 9)
			{
				return -1;
			}
			iSum = iSum + (str[i] - 48 ) * getNum(iLength,i);
		}
		return iSum;
	}

	bool parserSize(char * str,int * iWidth , int * iHeight)
	{
		char buf[100];
		char * strHead,*strTail;

		strTail = strstr(str,"matrix");
		if(strTail == NULL)
		{
			return false;
		}
		strTail = strstr(strTail,"(");
		if(strTail == NULL)
		{
			return false;
		}
		strHead = strTail + 1;
		strTail = strstr(strTail + 1,",");
		if(strTail == NULL)
		{
			return false;
		}
		memcpy(buf,strHead,strTail-strHead);
		buf[strTail-strHead] = 0;		
		*iWidth = getNumber(buf);
		if(*iWidth < 0)
		{
			return false;
		}
		strHead = strTail + 1;
		strTail = strstr(strTail + 1,")");
		if(strTail == NULL)
		{
			return false;
		}
		memcpy(buf,strHead,strTail-strHead);
		buf[strTail-strHead] = 0;
		*iHeight = getNumber(buf);
		if(*iHeight < 0)
		{
			return false;
		}
		return true;
	}

	string MatrixUtil::retStringFromMatrixP()
	{
		
		char buf[1000];
		buf[0] = '<';
		int iLength = 1;
		for(int i=0;i<iSIZE;i++)
		{
			integer iTemp(P[i]);
			string strTemp = iTemp.to_string();
			strcpy(buf+iLength,strTemp.cstring());
			iLength +=  1;
			buf[iLength] = ',';
			iLength +=1;
		}
		buf[iLength-1] = '>';
		buf[iLength] = 0;
		string strRes(buf);
		return strRes;
	}

	void print_matrix(integer_matrix m)
	{
		cout<<m.dim1() <<" "<<m.dim2()<<endl;
		for(int i=0;i<= m.dim1();i++)
		{
			for(int j=0;i<= m.dim2();j++)
			{
				cout << setw(5) << m[i][j];
			}
			cout << endl;
		}
	}

	void MatrixUtil::parserRandom(char * strInput)
	{
		char * head,*tail ;
		char buf[1000];
		int iRow = 0;
		int iCol = 0;
		iSIZE = 0;
		iErrorCode = 0;

		head = strInput;
		tail = strchr(strInput,'*');
		
		while (tail!=NULL)
		{			
			memcpy(buf,head,tail-head);
			if(parserSize(buf,&iRow,&iCol) == NULL)
			{
				iErrorCode = -1;
				return;
			}		
			if(iSIZE == 0)
			{
				P[iSIZE] = iRow;
				P[iSIZE+1] = iCol;
			}
			else if(iRow != P[iSIZE])
			{
				iErrorCode = -2;
				return;
			}
			else
			{
				P[iSIZE] = iRow;
				P[iSIZE+1] = iCol;
			}

			iSIZE++;
			
			head = tail + 1;
			tail=strchr(tail+1,'*');
		}

		memcpy(buf,head,strlen(head));

		if(parserSize(buf,&iRow,&iCol) == NULL)
		{
			iErrorCode = -1;
			return;
		}
		if(iRow != P[iSIZE])
		{
			iErrorCode = -2;
			return;
		}
		else
		{
			P[iSIZE] = iRow;
			P[iSIZE+1] = iCol;
			iSIZE++;
		}
		iSIZE++;
	}

	MatrixUtil::MatrixUtil()
	{

		for(int i = 0;i<cSIZEMAX+1;i++)
		{			
			for(int j = 0;j<cSIZEMAX+1;j++)
			{
				M[i][j] = 0;
				S[i][j] = 0;
			}
		}
		alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		errorPresent = false;
		return;
	}

	MatrixUtil::MatrixUtil(char * strInput)
	{
		parserRandom(strInput);

		if(iSIZE > cSIZEMAX)
		{
			iErrorCode = -3;
			return;
		}

		for(int i = 0;i<cSIZEMAX+1;i++)
		{			
			for(int j = 0;j<cSIZEMAX+1;j++)
			{
				M[i][j] = 0;
				S[i][j] = 0;
			}
		}
		alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		errorPresent = false;
		return;
	}

	MatrixUtil::~MatrixUtil()
	{
	
	}

	
	void MatrixUtil::MatrixChainOrder(int size)
	{
		int n = size-1;
		for(int L = 2; L <= n ; L++)
		{
			for(int i = 1; i <= n - L + 1 ; i++)
			{
				int j = i + L - 1;
				M[i][j] = MAX;
				for(int k = i;k <= j - 1;k ++)
				{
					int q = M[i][k] + M[k+1][j] + P[i-1] * P[k] * P[j];
					if(q < M[i][j])
					{	
						M[i][j] = q;
						S[i][j] = k;
						//cout<<i<<" "<<j<<" "<<M[i][j]<<endl;
					}
				}
			}
		}
	}


	
	int MatrixUtil::Recursive_Matrix(int i, int j)
	{
		int q;

		if( i == j )
			return 0;
		else
		{
			M[i][j] = MAX;
			for(int k = i; k <= j - 1; k++)
			{
				q =  Recursive_Matrix(i, k);
				q += Recursive_Matrix( k+1, j);
				q +=  P[i] * P[k + 1] * P[j + 1];
				if( q < M[i][j])
				   {
					   M[i][j] = q;
					   S[i][j] = k+1;
					}

			}
		}
		return M[i][j];
	}
	
	void MatrixUtil::Print_M()
	{
		for(int i = 1; i <= iSIZE; i++)
		{
			for(int j = 1; j <= iSIZE; j++)
			{
				cout << setw(7) << M[i][j];
			}
			cout << endl;
		}
		cout<<"-----------------------------------------------------"<<endl;
		for(int i = 1; i <= iSIZE; i++)
		{
			for(int j = 1; j <= iSIZE; j++)
			{
				cout << setw(7) << S[i][j];
			}
			cout << endl;
		}
	}
	void MatrixUtil::Print_M1()
	{
		cout<<"Matrix m:"<<endl;
		for(int x = 0; x < iSIZE+1; x++)
		{
			for(int y = 0; y < iSIZE+1; y++)
			{
				cout << setw(5) << M[x][y];
			}
			cout << endl;
		}
		cout<<"-----------------------------------------------------------"<<endl;
		cout<<"Matrix s:"<<endl;
		for(int i = 0; i < iSIZE+1; i++)
		{
			for(int j = 0; j < iSIZE+1; j++)
			{
				cout << setw(5) << S[i][j];
			}
			cout << endl;
		}
	}

	string MatrixUtil::PrintParenthese(int a, int b, int i, int j)
	{
		if (j - i == 1)
			 return alpha.sub(a, b+1-1);
		else if(S[i][j] == i)
			return alpha.sub(a, a+1-1) + "(" + PrintParenthese(a+1, b, i+1, j) + ")";
		else if(S[i][j] == j-1)
			return "(" + PrintParenthese(a, b-1, i, j-1) + ")" + alpha.sub(b, b+1-1);
		else
		{
			 int x = S[i][j];
			 return "(" + PrintParenthese(a, x-1, i, x) + ")" +
					"(" + PrintParenthese(x, b, x+1, j) + ")";
		}
	}

	int MatrixUtil::OptimizeCost()
	{
		return M[1][iSIZE-1];
	}

	int MatrixUtil::NormalCost()
	{
		int result = 0;
		for(int i =0;i<iSIZE-2;i++)
		{
			result += P[0]*P[i+1]*P[i+2];
		}
		return result;
	}
	integer_matrix MatrixUtil::matrix_chain_multiply()
	{
		//truyen vao matrix vector
		//matrix(3,3,[-362,-385,-408,570,675,780,-362,-301,-240])
		/*
			chu y : du lieu dua vao cho cac vector la du lieu cua cac cot
			xem vi du ben duoi :
		*/
		  integer_vector v1(3),v2(3),v3(3);  //define two 3d-zero-vectors;
		  
		  v1[0] = -362;
		  v1[1] = 570;
		  v1[2] = -362;
		  //cout<<" vt 0 "<<v1[0]<<endl;
		  //cout<<" vt 1 "<<v1[1]<<endl;
		  
		  //v1=integer_vector(-362,570,-362);    //assign values 
          v2=integer_vector(-385,675,-301);
		  v3=integer_vector(-408,780,-240);
		  array<integer_vector> V(0,2);
		  V[0] = v1;
		  V[1] = v2;
		  V[2] = v3;
		  
		  integer_matrix A(V);
		 // A.transpo
		  integer_matrix B(V);
		  integer_matrix C(V);
		  //array<integer_matrix> matrixVector(0,cSIZEMAX);
		  matrixVector.resize(0,2);
		  matrixVector[0] = A;
		  matrixVector[1] = B;
		  matrixVector[2] = C;		  
		  //matrixVector = matrixVector1;
		  return chain_multiply(matrixVector, 0, matrixVector.size()-1);
	}

	integer_matrix MatrixUtil::chain_multiply( array<integer_matrix> v, int i, int j)
	{
		if(j>i)
		{
			integer_matrix m;
			integer_matrix x = chain_multiply(v, i, S[i][j]);
			integer_matrix y = chain_multiply(v, S[i][j] + 1, j);
			m = x*y;			
			return m;
		}
		else
			return v[i];
	}

	void MatrixUtil::processCommand(string text)
	{
		iErrorCode = 0;
		if (strcmp(text.cstring(),"") == 0)
		{
			iErrorCode = -10;//input string is nulll
		}
		else
		{
			iSIZE = 0;
			for(int i = 0;i<cSIZEMAX+1;i++)
			{			
				for(int j = 0;j<cSIZEMAX+1;j++)
				{
					M[i][j] = 0;
					S[i][j] = 0;
				}
			}
			string str=" ";
			text.del_all(str);
			//removeSpaces(text.c_str());
			iSequenceNumber = 0;
			parseInput(text,&iSequenceNumber);
			iSIZE = iSIZE + 2;
			if(iErrorCode == 0)
			{
				MatrixChainOrder(iSIZE);
				Print_M1();
				string result = PrintParenthese(0,iSIZE-2,1,iSIZE-1);
				cout<<"-----------------------------------------------------------"<<endl;
				cout<<"Optimize parenthese ="<<result<<endl;
				cout<<"-----------------------------------------------------------"<<endl;
				int normalCost = NormalCost();
				cout<<"Normal cost = "<<normalCost<<endl;
				cout<<"-----------------------------------------------------------"<<endl;
				int optimizeCost = OptimizeCost();
				cout<<"Optimize cost = "<<optimizeCost<<endl;
				cout<<" "<<endl;
				 matrix_result = chain_multiply(matrixVector, 0, matrixVector.size()-1);
				cout<<"Result of Multiplied Matrix:"<<endl;
				cout<<matrix_result<<endl;
			}
		}
	}

	void MatrixUtil::parseInput(string text,int * sequenceNumber)
	{
		integer rows = 0, cols = 0;
		//string text(str);
		if (!text.contains("matrix"))
		{
			iErrorCode = -11;//Missing Keyword Matrix for entry
			return ;
		}
		else
		{
			int openParensPos = text.pos('('); 
            int closeParensPos = text.pos(')');
			if (openParensPos == -1)
			{
				iErrorCode = -12; //Missing opening parenthesis for matrix
				return ;
			}
			else if (closeParensPos == -1)
			{
				iErrorCode = -13; //Missing closing parenthesis for matrix
				return ;
			}
			else
			{
				string inputParams = text.sub(openParensPos + 1, closeParensPos-1); 
				int firstCommaPos = inputParams.pos(',');
				if (firstCommaPos != -1)
				{	
					leda::set_error_handler(leda::exception_error_handler);
					try
					{
						rows.from_string(inputParams.sub(0, firstCommaPos-1));
						if (rows == 0)
						{
							iErrorCode = -15; //Row cannot be 0 for matrix
							return ;
						}
						else
						{
							if(iSIZE > 0)
							{
								if(P[iSIZE] != rows.to_long())	
								{
									errorPresent = true;
									iErrorCode = -2;//Column cannot be 0 for matrix
									return ;
								}
							}
							P[iSIZE] = rows.to_long();
							inputParams = inputParams.sub(firstCommaPos + 1,inputParams.length()-1);
							//cout<<"Input string : " <<inputParams.cstring()<<endl;
						}
					}
					catch(leda::leda_exception e) 
					{
						iErrorCode = -22; // Missing at the row
						errorPresent = true;
					}

					if (!errorPresent)
					{
						int secondCommaPos = inputParams.pos(',');
						if (secondCommaPos != -1)
						{
							leda::set_error_handler(leda::exception_error_handler);
							try
							{								
								cols.from_string(inputParams.sub(0,secondCommaPos-1));
								if (cols == 0)
								{
									errorPresent = true;
									iErrorCode = -17;//Column cannot be 0 for matrix
									return ;
								}
								else
								{
									
									P[iSIZE + 1] = cols.to_long();
									inputParams = inputParams.sub(secondCommaPos + 1,inputParams.length()-1);
								}
							}
							catch(leda::leda_exception e) 
							{
								iErrorCode = -23; // Missing at the col
								errorPresent = true;
							}
							
							if (!errorPresent)
							{
								int openBracketsPos = inputParams.pos('[');
								int closeBracketsPos = inputParams.pos(']');
								if (openBracketsPos == -1)
								{
									iErrorCode = -18; //Missing opening bracket for matrix
									return ;
								}
								else if (closeBracketsPos == -1)
								{
									iErrorCode = -19; //Missing closing bracket for matrix
									return ;
								}
								else
								{
									inputParams = inputParams.sub(openBracketsPos + 1,closeBracketsPos-1);
									int numOfEntries = rows.to_long() * cols.to_long();
									int* entries = (int *) malloc(numOfEntries * sizeof(int));
									getValues(numOfEntries, inputParams,entries, sequenceNumber);
									if (!errorPresent)
									{
										integer_matrix matrix;
										getMatrix(rows.to_long(),cols.to_long(),entries,&matrix);
										//cout<<"Testing Matrix:"<<endl;
										//cout<<matrix<<endl;
										matrixVector.resize(0,*sequenceNumber);
										matrixVector[*sequenceNumber] = matrix;
										if (closeParensPos + 1 != text.length())
										{
											if (text.get(closeParensPos + 1) == '*')
											{
												iSIZE += 1;
												*sequenceNumber += 1; 
												parseInput(text.sub(closeParensPos + 2,text.length() - 1),sequenceNumber);
											}
											else
											{
											   errorPresent = true;		
											   iErrorCode = -21;//Syntax error in expression after matrix
											}
										}
									}
                                        
								}
							}
						
						}
						else
						{
							errorPresent = true;	
							iErrorCode = -16; //Missing second comma or input parameters not present for matrix
						}

					}					
				}
				else
				{
					iErrorCode = -14;//missing the first comma
				}
			}

		}
	}

	void MatrixUtil::getMatrix(int rows, int cols, int * entries,integer_matrix *matrix)
	{
		
		array<integer_vector> V(cols);
		for(int i=0;i<cols;i++)
		{
			integer_vector vector(rows );
			for(int j = 0 ;j<rows;j++)
			{
				vector[j] = entries[j * cols + i];
			}
			V[i] = vector;
		}
		integer_matrix m(V);
		*matrix = m;
	}

	bool MatrixUtil::getValues(int numOfEntries, string input, int *entries,int *sequenceNumber)
	{		
		integer temp;
		int entryNumber = 0;
		  while ((input.length() > 0) && (!errorPresent))
		  {
			 if (entryNumber == numOfEntries)
			 {
				errorPresent = true;
			 }
			 else
			 {
				int posOfComma = input.pos(",");
				string numberString;
				if (posOfComma == -1)
				{
				   numberString = input;
				}
				else
				{
				   numberString = input.sub(0, posOfComma -1);
				}
				leda::set_error_handler(leda::exception_error_handler);
				try
				{
					entries[entryNumber] = temp.from_string(numberString).to_long();
				}
				catch(leda::leda_exception e) 
				{
					errorPresent = true;
					iErrorCode = -24;//TheNumberInMatrixError
				}

				if (!errorPresent)
				{
				   if (posOfComma == -1)
					  input = "";
				   else
					   input = input.sub(posOfComma + 1 , input.length() - 1);
				   entryNumber++;
				}
			 }
		  }
		  if ((!errorPresent) && (entryNumber != numOfEntries))
		  {
			 errorPresent = true;
			 iErrorCode = -20 ;//Too few entries for matrix
		  }
		return true;
	}

	void MatrixUtil::removeSpaces(char * text)
    {
		int iLen = 0;
		int iCount = 0;
		iLen = strlen(text);
		char * str1,*pTemp;
		str1 = (char *) malloc(iLen + 1);
		memcpy(str1,text,iLen);
		str1[iLen] = 0;
		do
		{
			iLen = strlen(str1);
			pTemp = strchr(str1,' ');
			if(pTemp == NULL)
			{
				break;
			}
			iCount = pTemp-str1;
			memcpy(pTemp,pTemp+1,iLen-iCount-1);
			str1[iLen - 1] = 0;

		}while(1);

		iLen = strlen(str1);
		memcpy(text,str1,iLen);
		text[iLen] = 0;
    }

	
	
	


